SCCPC2026 J 献给空白的无败冠冕 题解
题目链接：QOJ Contest 3789 Problem J
棋盘只有两行，因此一条路径完全由下移列 $k$ 决定。题目要我们填出一个棋盘，使得“白让自己拿到最多硬币”的策略会唯一地选择某条路径，但这条路径并不是让空收益最小的正确选择。
先把真正影响路径比较的格子提出来。无论白选择哪条路径，左上角 $a_{1,1}$ 和右下角 $a_{2,n}$ 都一定会被经过，所以它们不会影响路径之间的优劣。相邻两条路径的差别只来自每两列之间的一对斜对角格子，记
$$
x_i=a_{1,i+1},\qquad y_i=a_{2,i}\qquad (1\le i<n).
$$
若原格子已经给定，对应变量的上下界相等；若原格子为 $-1$，上下界就是 $[1,10^9]$。记为
$$
\mathrm{lx}_i\le x_i\le \mathrm{ux}_i,\qquad
\mathrm{ly}_i\le y_i\le \mathrm{uy}_i.
$$
白选择下移列 $k$ 后，没有被白拿走的部分分成上方剩余和下方剩余两段：
$$
U_k=\sum_{i=k}^{n-1}x_i,\qquad
L_k=\sum_{i=1}^{k-1}y_i.
$$
空会选择自己能拿到更多的一边，所以白真正应该最小化的是
$$
G_k=\max(U_k,L_k).
$$
但错误策略是让白自己拿到最多硬币。设棋盘总和为 $S$，白选择 $k$ 时拿到 $S-U_k-L_k$，所以错误策略等价于最小化
$$
R_k=U_k+L_k.
$$
我们要构造的就是这样一种局面：$R_k$ 有唯一最小点 $p$，但 $p$ 不是 $G_k$ 的最小点。
先刻画“$R_p$ 唯一最小”。相邻两条路径满足
$$
U_{k+1}=U_k-x_k,\qquad L_{k+1}=L_k+y_k,
$$
因此
$$
R_{k+1}-R_k=y_k-x_k.
$$
若 $R_p$ 是唯一最小，那么从 $p$ 往左或往右走，$R$ 都必须严格变大。写成条件就是
$$
\sum_{i=t}^{p-1}(x_i-y_i)>0\qquad (t<p),
$$
以及
$$
\sum_{i=p}^{t}(y_i-x_i)>0\qquad (t\ge p).
$$
也就是说，$p$ 左边所有后缀和为正，$p$ 右边所有前缀和为正。
接着看怎样让这个唯一选择变成错误选择。假设白唯一选择了 $p$。如果 $U_p>L_p$，空在路径 $p$ 下主要拿上方剩余部分；这时把下移列向右挪，会减少上方剩余、增加下方剩余。若某个更右的路径能让 $G$ 变小，那么相邻的 $p+1$ 已经能做到。左边的情况完全对称。因此只需要尝试两类构造：让 $p+1$ 比 $p$ 更优，或者让 $p-1$ 比 $p$ 更优。下面只描述右侧反例；左侧可以把序列反过来用同样的方法处理。
右侧反例要求 $G_{p+1}<G_p$。由
$$
U_{p+1}=U_p-x_p,\qquad L_{p+1}=L_p+y_p
$$
可知，只要
$$
L_p+y_p<U_p
$$
就够了。展开后为
$$
\sum_{i=p}^{n-1}x_i-y_p>\sum_{i=1}^{p-1}y_i.
$$
于是我们希望左边尽量大、右边尽量小，同时还要维持 $R_p$ 唯一最小。
先处理 $p$ 左边。为了让左侧所有后缀和尽量容易为正，并且让上式右边尽量小，取
$$
x_i=\mathrm{ux}_i,\qquad y_i=\mathrm{ly}_i\qquad (i<p).
$$
令 $e_i=\mathrm{ux}_i-\mathrm{ly}i$。左半部分可行，当且仅当 $e_1,\ldots,e{p-1}$ 的所有后缀和都为正；若可行，上式右边能取到的最小值是
$$
\mathrm{leftMinY}p=\sum{i=1}^{p-1}\mathrm{ly}_i.
$$
后缀和是否全为正可以线性预处理。设
$$
s_i=\min_{1\le t\le i}\sum_{j=t}^{i}e_j,
$$
则 $s_i=e_i+\min(0,s_{i-1})$，只要 $s_{p-1}\ge 1$，左侧就可行。
再看中心位置 $p$。为了让 $p$ 右边的 $R$ 一开始严格上升，需要 $y_p-x_p>0$。记
$$
z=y_p-x_p.
$$
它必须满足
$$
\mathrm{ly}_p-\mathrm{ux}_p\le z\le \mathrm{uy}_p-\mathrm{lx}_p,\qquad z\ge 1.
$$
我们会取满足所有条件的最小 $z$，因为这样留给右半边的限制最宽松。
对 $i>p$，为了让右侧反例的不等式左边尽量大，先取 $y_i=\mathrm{uy}_i$，再令 $w_i=x_i-y_i$。于是
$$
L_i\le w_i\le U_i,
$$
其中
$$
L_i=\mathrm{lx}_i-\mathrm{uy}_i,\qquad U_i=\mathrm{ux}_i-\mathrm{uy}_i.
$$
右侧所有前缀和为正等价于
$$
\sum_{i=p+1}^{t}w_i\le z-1\qquad (t>p).
$$
记
$$
\mathrm{need}p=\max\left(0,\max{t>p}\sum_{i=p+1}^{t}L_i\right).
$$
那么为了让右半边至少有解，必须让 $z\ge \mathrm{need}_p+1$。综合中心位置的上下界，最小可行的
$$
z=\max\left(1,\mathrm{ly}_p-\mathrm{ux}_p,\mathrm{need}_p+1\right).
$$
如果这个值超过 $\mathrm{uy}_p-\mathrm{lx}_p$，当前 $p$ 就不可能作为右侧反例中心。
确定 $z$ 后，设 $C=z-1$。右半边还要在所有前缀和不超过 $C$ 的条件下最大化 $\sum_{i=p+1}^{n-1}w_i$。这个最大值为
$$
\mathrm{best}p=
\min\left(
\sum{i=p+1}^{n-1}U_i,
C+\min_{q\ge p+2}\sum_{i=q}^{n-1}U_i
\right).
$$
可以理解成：如果全取上界不会出问题，就全取上界；否则某个前缀会先被 $C$ 卡住，之后的后缀继续尽量取上界。这个式子可以用 $U_i$ 的后缀和与后缀最小值 $O(1)$ 求出。
于是右侧不等式左边能达到的最大值是
$$
\mathrm{maxRight}p=-z+\sum{i=p+1}^{n-1}\mathrm{uy}_i+\mathrm{best}_p.
$$
右侧反例存在，当且仅当左半边可行，并且
$$
\mathrm{maxRight}_p>\mathrm{leftMinY}_p.
$$
这些量都能通过前缀和、后缀和、最大前缀下界、后缀最小值在线性时间内预处理，因此可以枚举每个 $p$ 判断。
找到可行的 $p$ 后，构造也沿用判定时的取法。左边取 $x_i=\mathrm{ux}_i,\ y_i=\mathrm{ly}_i$；中心选一组满足 $y_p-x_p=z$ 且在上下界内的 $(x_p,y_p)$；右边固定 $y_i=\mathrm{uy}_i$，再构造 $w_i=x_i-y_i$。
构造 $w_i$ 时，需要满足 $L_i\le w_i\le U_i$，并且所有前缀和不超过 $C$。可以先从左到右算每个前缀和的最小可能值 $lo$，再算最大可能值 $hi$ 并用 $C$ 截断，最后从最终前缀和倒推。若当前前缀和为 $cur$，正在倒推第 $t$ 个变量，则上一个前缀和 $pre$ 需要落在
$$
[lo_{t-1},hi_{t-1}]\cap[cur-U_t,cur-L_t]
$$
中。任选一个合法的 $pre$，令 $w_t=cur-pre$ 即可。判定阶段已经保证可行，所以这个倒推一定能成功。
如果右侧反例找不到，就对称地尝试左侧反例；两边都找不到则输出 $-1$。最后把构造出的变量还原成棋盘：
$$
a_{1,i+1}=x_i,\qquad a_{2,i}=y_i.
$$
没有参与变量的 $a_{1,1}$ 和 $a_{2,n}$ 不影响路径选择，若原本是 $-1$，填 $1$ 即可，否则保留原值。
总时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。